#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>


// FUNCTION: 定义动态数组
typedef int ElemType;

typedef struct {
	ElemType *elem;//存储元素的起始地址
	int TableLen;//元素个数
} SSTable;


// FUNCTION: 随机数生成
void ST_Init(SSTable &ST, int len) {
	// NOTE: 变量初始化
	// STEP: 多申请了一个位置,为了存哨兵
	ST.TableLen = len + 1;

	// STEP: 申请动态数组实际空间
	ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);

	// STEP: 存放赋值变量是的索引
	int i;


	// NOTE: 生成随机数
	srand(time(NULL));


	// NOTE: 将数据存储到数组中
	// HINT: 为啥这里零号位置也存放了随机了数据？是为折半查找服务的。
	for (i = 0; i < ST.TableLen; i++) {
		ST.elem[i] = rand() % 100;
	}
}


// FUNCTION: 输出数组中全部元素
void ST_print(SSTable ST) {
	for (int i = 0; i < ST.TableLen; i++) {
		printf("%3d", ST.elem[i]);
	}

	printf("\n");
}


// FUNCTION: 交换数组元素
void swap(ElemType &a, ElemType &b) {
	ElemType tmp;
	tmp = a;
	a = b;
	b = tmp;
}


// HINT: 王道书的写法，我们重写
// FUNCTION: 调整以k为根结点的子树（小元素下坠）
void AdjustDown_wangdao(ElemType A[], int k, int len) {
	// NOTE: 用A[0]暂存结点k
	A[0] = A[k];


	// NOTE: 小元素下坠
	for (int i = 2 * k; i <= len; i *= 2) {
		// STEP: 判断k所指结点的左右孩子大小。得到较大的孩子结点索引值i
		// HINT: i < len的目的是：使得A[i + 1]必定存在
		if (i < len && A[i] < A[i + 1]) {
			++i;
		}

		// STEP: 判断当前结点k与孩子结点i的大小关系
		if (A[0] >= A[i]) {
			// 如果是。则证明所有子树都满足大根堆。可退出递归
			break;
		} else {
			// 如果不是。则应该继续调整子树，并一直递归下去。
			// HINT: 因为不能保证父结点被换下后，以该结点为父结点的子树依然是大顶堆的形式。所以，需要递归加以判断、调整。
			// 子父对调
			A[k] = A[i];

			// 将换下的结点用k指向
			k = i;
		}
	}


	// NOTE: 最终让小元素安放在k所指位置
	A[k] = A[0];
}


// FUNCTION: 建立大根堆（又名：大顶堆）
// REVIEW: 如果把初始序列看成是经“层序遍历”的二叉树得到的。那么，由二叉树的性质：“在顺序存储的完全二叉树中，非终端节点的编号为i≤⌊n/2⌋”。为了建立起一个大根堆，从二叉树的视角看：只要从最底层的非终端结点开始调整，并逐层往树根结点逐层递归。最终就可以完成实现大根堆的建立。那么，等价说来，顺序存储的二叉树序列的调整应为：将编号从i≤⌊n/2⌋的元素开始，每次调整完在往前一个元素走一个，一直走到第一个元素调整完。就算建成了一个大顶堆了。
void Build_Max_Heap(ElemType A[], int len) {
	// NOTE: 从数组元素为⌊len / 2⌋开始进行调整，并且逐次往前，直到第一个元素为止。
	for (int i = len / 2; i > 0; i--) {
		AdjustDown_wangdao(A, i, len);
	}
}


// FUNCTION: 堆排序
void HeapSort_wangdao(ElemType A[], int len) {
	// NOTE: 临时变量申请
	// HINT: i始终指向当前待排元素序列中最后一个（即堆低元素）
	int i;


	// NOTE: 建立大顶堆
	Build_Max_Heap(A, len);


	// NOTE: 实现堆排序
	for (i = len; i > 1; --i) {
		// STEP: 堆顶元素与堆低元素互换
		swap(A[i], A[1]);

		// STEP: 把剩余的元素处理称为堆
		// HINT: 当堆顶元素与堆低元素互换后，我们认为堆低元素就不在堆内了。恰好i之中指向当前被调前，堆内最后一个有效元素。故，当排除掉最后一个元素后，现在堆内元素个数仅为i - 1。
		AdjustDown_wangdao(A, 1, i - 1);
	}
}


// FIXME: 自己实现，所有元素参与排序
/*
// FUNCTION: 调整以索引值为k的子树，使之成为大根堆的形式
void AdjustDown(ElemType A[], int k, int len) {
	// NOTE: 变量声明
	// STEP: 根结点的索引记为dad
	int dad = k;

	// STEP: 左孩子的索引记为son
	int son = 2 * dad + 1;

	// NOTE:
	while (son <= len) {
		// STEP: 看下有没有右孩子？比较左右孩子，选大的
		// HINT: 这里“son + 1 <= len”的不等号有讲究。取不取等号，取决于我传入的len。
		if (son + 1 <= len && A[son] < A[son + 1]) {
			++son;
		}

		// STEP: 比较较大的孩子和父亲谁大？
		if (A[son] > A[dad]) {
			// 交换二者的值
			swap(A[son], A[dad]);

			// HINT: 发生交换后，还需验证被换下的结点作为局部子树的树根，这棵树是否为大根堆？如果不是则需要继续调整。
			// 把孩子的索引给原来的父亲
			dad = son;

			//
			son = 2 * dad + 1;
		} else {
			break;
		}
	}
}


void HeapSort(ElemType A[], int len) {
	// NOTE: 申请临时变量
	int i;


	// NOTE: 建立大顶堆
	for (i = len / 2; i >= 0; i--) {
		AdjustDown(A, i, len);
	}


	// NOTE: 交换顶部和数组最后一个元素
	swap(A[0], A[len]);

	for (i = len - 1; i > 0; i--) {
		//剩下元素调整为大根堆
		AdjustDown(A, 0, i);
		swap(A[0], A[i]);
	}
}
*/


int main() {
	setbuf(stdout, NULL);


	// NOTE: Variable declaration
	// STEP: 声明动态数组
	SSTable ST;

	// STEP: 声明一组数
	ElemType A[10] = {64, 94, 95, 79, 69, 84, 18, 22, 12, 78};


	// NOTE: 数组元素赋值
	// HINT: 实际申请了11个元素空间
	ST_Init(ST, 10);
	memcpy(ST.elem, A, sizeof(A));

	printf("Original sequence is: ");
	ST_print(ST);


	// NOTE: 堆排序
	// HINT: 王道书零号元素不参与排序
	HeapSort_wangdao(ST.elem, 9);

/*
	// HINT: 所有元素参与排序
	HeapSort(ST.elem, 9);
*/

	return 0;
}